// RB tree implementation -*- C++ -*-

// Copyright (C) 2001-2013 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/*

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Hewlett-Packard Company makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 */

/** @file bits/stl_tree.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{map,set}

 */

#ifndef _STL_TREE_H

#define _STL_TREE_H 1

#include <bits/stl_algobase.h>

#include <bits/allocator.h>

#include <bits/stl_function.h>

#include <bits/cpp_type_traits.h>

#if __cplusplus >= 201103L

#include <bits/alloc_traits.h>

#endif

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // Red-black tree class, designed for use in implementing STL

  // associative containers (set, multiset, map, and multimap). The

  // insertion and deletion algorithms are based on those in Cormen,

  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,

  // 1990), except that

  //

  // (1) the header cell is maintained with links not only to the root

  // but also to the leftmost node of the tree, to enable constant

  // time begin(), and to the rightmost node of the tree, to enable

  // linear time performance when used with the generic set algorithms

  // (set_union, etc.)

  // 

  // (2) when a node being deleted has two children its successor node

  // is relinked into its place, rather than copied, so that the only

  // iterators invalidated are those referring to the deleted node.

  enum _Rb_tree_color { _S_red = false, _S_black = true };

  struct _Rb_tree_node_base

  {

    typedef _Rb_tree_node_base* _Base_ptr;

    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color	_M_color;

    _Base_ptr		_M_parent;

    _Base_ptr		_M_left;

    _Base_ptr		_M_right;

    static _Base_ptr

    _S_minimum(_Base_ptr __x)

    {

      while (__x->_M_left != 0) __x = __x->_M_left;

      return __x;

    }

    static _Const_Base_ptr

    _S_minimum(_Const_Base_ptr __x)

    {

      while (__x->_M_left != 0) __x = __x->_M_left;

      return __x;

    }

    static _Base_ptr

    _S_maximum(_Base_ptr __x)

    {

      while (__x->_M_right != 0) __x = __x->_M_right;

      return __x;

    }

    static _Const_Base_ptr

    _S_maximum(_Const_Base_ptr __x)

    {

      while (__x->_M_right != 0) __x = __x->_M_right;

      return __x;

    }

  };

  template<typename _Val>

    struct _Rb_tree_node : public _Rb_tree_node_base

    {

      typedef _Rb_tree_node<_Val>* _Link_type;

      _Val _M_value_field;

#if __cplusplus >= 201103L

      template<typename... _Args>

        _Rb_tree_node(_Args&&... __args)

	: _Rb_tree_node_base(),

	  _M_value_field(std::forward<_Args>(__args)...) { }

#endif

    };

  _GLIBCXX_PURE _Rb_tree_node_base*

  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

  _GLIBCXX_PURE const _Rb_tree_node_base*

  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();

  _GLIBCXX_PURE _Rb_tree_node_base*

  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();

  _GLIBCXX_PURE const _Rb_tree_node_base*

  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();

  template<typename _Tp>

    struct _Rb_tree_iterator

    {

      typedef _Tp  value_type;

      typedef _Tp& reference;

      typedef _Tp* pointer;

      typedef bidirectional_iterator_tag iterator_category;

      typedef ptrdiff_t                  difference_type;

      typedef _Rb_tree_iterator<_Tp>        _Self;

      typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;

      typedef _Rb_tree_node<_Tp>*           _Link_type;

      _Rb_tree_iterator()

      : _M_node() { }

      explicit

      _Rb_tree_iterator(_Link_type __x)

      : _M_node(__x) { }

      reference

      operator*() const

      { return static_cast<_Link_type>(_M_node)->_M_value_field; }

      pointer

      operator->() const

      { return std::__addressof(static_cast<_Link_type>

				(_M_node)->_M_value_field); }

      _Self&

      operator++()

      {

	_M_node = _Rb_tree_increment(_M_node);

	return *this;

      }

      _Self

      operator++(int)

      {

	_Self __tmp = *this;

	_M_node = _Rb_tree_increment(_M_node);

	return __tmp;

      }

      _Self&

      operator--()

      {

	_M_node = _Rb_tree_decrement(_M_node);

	return *this;

      }

      _Self

      operator--(int)

      {

	_Self __tmp = *this;

	_M_node = _Rb_tree_decrement(_M_node);

	return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      _Base_ptr _M_node;

  };

  template<typename _Tp>

    struct _Rb_tree_const_iterator

    {

      typedef _Tp        value_type;

      typedef const _Tp& reference;

      typedef const _Tp* pointer;

      typedef _Rb_tree_iterator<_Tp> iterator;

      typedef bidirectional_iterator_tag iterator_category;

      typedef ptrdiff_t                  difference_type;

      typedef _Rb_tree_const_iterator<_Tp>        _Self;

      typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;

      typedef const _Rb_tree_node<_Tp>*           _Link_type;

      _Rb_tree_const_iterator()

      : _M_node() { }

      explicit

      _Rb_tree_const_iterator(_Link_type __x)

      : _M_node(__x) { }

      _Rb_tree_const_iterator(const iterator& __it)

      : _M_node(__it._M_node) { }

      iterator

      _M_const_cast() const

      { return iterator(static_cast<typename iterator::_Link_type>

			(const_cast<typename iterator::_Base_ptr>(_M_node))); }

      reference

      operator*() const

      { return static_cast<_Link_type>(_M_node)->_M_value_field; }

      pointer

      operator->() const

      { return std::__addressof(static_cast<_Link_type>

				(_M_node)->_M_value_field); }

      _Self&

      operator++()

      {

	_M_node = _Rb_tree_increment(_M_node);

	return *this;

      }

      _Self

      operator++(int)

      {

	_Self __tmp = *this;

	_M_node = _Rb_tree_increment(_M_node);

	return __tmp;

      }

      _Self&

      operator--()

      {

	_M_node = _Rb_tree_decrement(_M_node);

	return *this;

      }

      _Self

      operator--(int)

      {

	_Self __tmp = *this;

	_M_node = _Rb_tree_decrement(_M_node);

	return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      _Base_ptr _M_node;

    };

  template<typename _Val>

    inline bool

    operator==(const _Rb_tree_iterator<_Val>& __x,

               const _Rb_tree_const_iterator<_Val>& __y)

    { return __x._M_node == __y._M_node; }

  template<typename _Val>

    inline bool

    operator!=(const _Rb_tree_iterator<_Val>& __x,

               const _Rb_tree_const_iterator<_Val>& __y)

    { return __x._M_node != __y._M_node; }

  void

  _Rb_tree_insert_and_rebalance(const bool __insert_left,

                                _Rb_tree_node_base* __x,

                                _Rb_tree_node_base* __p,

                                _Rb_tree_node_base& __header) throw ();

  _Rb_tree_node_base*

  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,

			       _Rb_tree_node_base& __header) throw ();

  template<typename _Key, typename _Val, typename _KeyOfValue,

           typename _Compare, typename _Alloc = allocator<_Val> >

    class _Rb_tree

    {

      typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other

              _Node_allocator;

    protected:

      typedef _Rb_tree_node_base* 		_Base_ptr;

      typedef const _Rb_tree_node_base* 	_Const_Base_ptr;

    public:

      typedef _Key 				key_type;

      typedef _Val 				value_type;

      typedef value_type* 			pointer;

      typedef const value_type* 		const_pointer;

      typedef value_type& 			reference;

      typedef const value_type& 		const_reference;

      typedef _Rb_tree_node<_Val>* 		_Link_type;

      typedef const _Rb_tree_node<_Val>*	_Const_Link_type;

      typedef size_t 				size_type;

      typedef ptrdiff_t 			difference_type;

      typedef _Alloc 				allocator_type;

      _Node_allocator&

      _M_get_Node_allocator() _GLIBCXX_NOEXCEPT

      { return *static_cast<_Node_allocator*>(&this->_M_impl); }

      const _Node_allocator&

      _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT

      { return *static_cast<const _Node_allocator*>(&this->_M_impl); }

      allocator_type

      get_allocator() const _GLIBCXX_NOEXCEPT

      { return allocator_type(_M_get_Node_allocator()); }